//
//  53_最大子数组和.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/4.
//

import UIKit
/**
 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

 子数组
 是数组中的一个连续部分。
 示例 1：

 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 输出：6
 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 示例 2：

 输入：nums = [1]
 输出：1
 示例 3：

 输入：nums = [5,4,-1,7,8]
 输出：23
 */
/// 动态规划实现（pd[i]以numb[i]结尾的最大连续子序列和）
class DPGetMaxSubArray {
    
    func QA() {
        print(maxSubArray([5,4,-1,7,8]))
    }
    
    func maxSubArray(_ nums: [Int]) -> Int {
        if nums.count == 0  { return 0 }
        var dp = Array(repeating: 0, count: nums.count)
        dp[0] = nums[0]
        for index in 1..<nums.count {
            let num = nums[index]
            if dp[index - 1] < 0 {
                dp[index] = num
            } else {
                dp[index] = dp[index - 1] + num
            }
        }
        
        var getMax = dp[0]
        for count in dp {
            getMax = max(getMax, count)
        }
        return getMax
    }
    
    /// 空间复杂度优化
    func maxSubArray1(_ nums: [Int]) -> Int {
        if nums.count == 0  { return 0 }
        var dp = nums[0]
        var getMax = dp
        for index in 1..<nums.count {
            let num = nums[index]
            if dp < 0 {
                dp = num
            } else {
                dp = dp + num
            }
            getMax = max(getMax, dp)
        }
        
        return getMax
    }
}
